package com.he.test;

/**
 * @description: 非递归实现N皇后问题
 * @Author: HCL
 * @Date: 2024/11/4 15:21
 */
public class QueenTest1 {

    final int N = 4;
    int[] q = new int[N + 1];//第i个皇后在第i行的q[i]列上

    /**
     * @Description 判断皇后位置是否合法
     * @Author HCL
     * @Date 2024/11/4 15:22
     * @Param
     * @Return
     */
    boolean check(int j) {
        boolean flag = true;
        for (int i = 1; i < j; i++) {
            // 判断是否在同一行 或 对角线上
            if (q[i] == q[j] || Math.abs(i - j) == Math.abs(q[i] - q[j])) {
                flag = false;
            }
        }
        return flag;
    }

    /**
     * @Description 求解N皇后方案
     * @Author HCL
     * @Date 2024/11/4 15:35
     * @Param
     * @Return
     */
    void queue() {
        //初始化
        for (int i = 1; i <= N; i++) {
            q[i] = 0;
        }

        int answer = 0;//方案数
        int j = 1;//正在摆放的位置
        while (j >= 1) {

            q[j] = q[j] + 1;//往后边的列摆放

            while (q[j] <= N && !check(j)) {//在棋盘范围内,但不满足皇后条件
                q[j] = q[j] + 1;
            }

            if (q[j] <= N) {//找到一个合法的位置

                if (j == N) {//找到N皇后的一组解
                    answer++;
                    System.out.print("方案：");
                    for (int i = 1; i <= N; i++) {
                        System.out.print(q[i]);
                    }
                    System.out.println();
                } else {
                    j++;
                }

            } else {//没有找到合法的摆放位置
                q[j] = 0;//还原第j个皇后的位置
                j--;//回溯
            }
        }
    }

    public static void main(String[] args) {
        new QueenTest1().queue();
    }
}
